/**************************************************************************
* File:            graph.h	                                              *
* Description:     Two implementations of graph - incidence list/matrix   *
* Author:          Zhuk Artsem, 399                                       *
**************************************************************************/

#pragma once

#include <vector>
#include <functional>
#include <memory>
#include <iostream>

struct Edge{
	int from, to;
	Edge(){}
	Edge(int from, int to) :from(from), to(to){}
	bool operator ==(const Edge &x)const{
		return x.from == from && x.to == to;
	}
	bool operator !=(const Edge &x)const{
		return !(*this == x);
	}
	bool operator <(const Edge &x)const{
		return from < x.from || (from == x.from && to < x.to);
	}
};


class Graph{
public:
	virtual int getVerticesNumber() const = 0;
	virtual std::vector<int> getIncidenceList(int vertex) const = 0;
	virtual ~Graph(){}
};

class ListBasedGraph :public Graph{
	int vertices_number_;
	int edges_number_;
	std::vector<std::vector<int> > incidence_list_;
public:
	ListBasedGraph(const std::vector<Edge> &edges,const int vertices_number_):
		vertices_number_(vertices_number_), incidence_list_(vertices_number_), edges_number_(edges.size()){

		for (auto &edge : edges){
			incidence_list_[edge.from].push_back(edge.to);
		}

	}

	std::vector<int> getIncidenceList(int vertex)const{
		return incidence_list_[vertex];
	}

	int getVerticesNumber()const{
		return vertices_number_;
	}

};

class MatrixGraph :public Graph{
	int vertices_number_;
	std::vector<std::vector<bool> >  incidence_matrix_;
public:
	MatrixGraph(const std::vector<Edge> &edges, const int vertices_number_) :vertices_number_(vertices_number_){
		incidence_matrix_.resize(vertices_number_);

		for (auto &row : incidence_matrix_){
			row.resize(vertices_number_);
		}

		for (auto &edge : edges){
			incidence_matrix_[edge.from][edge.to] = true;
		}
	}

	int getVerticesNumber()const{
		return vertices_number_;
	}

	std::vector<int> getIncidenceList(int vertex)const{
		std::vector<int> adjacent;

		for (int i = 0; i < vertices_number_; ++i)
		if (incidence_matrix_[vertex][i]){
			adjacent.push_back(i);
		}

		return adjacent;
	}
};

std::unique_ptr<Graph> makeCompactGraph(std::vector<Edge> edges, int vertices_number){
	size_t matrix_size = vertices_number * vertices_number;
	size_t list_size = 2 * edges.size() * sizeof(int);

	if (matrix_size < list_size)
		return std::unique_ptr<Graph> (new MatrixGraph(edges, vertices_number));
	else
		return std::unique_ptr<Graph> (new ListBasedGraph(edges, vertices_number));
}



